package com.xk._03真题骗._01数组_排序;

/*
 * @description: https://leetcode.cn/problems/sub-sort-lcci/
 * @author: xu
 * @date: 2022/10/27 6:17
 */
public class _面试题_16_16部分排序 {

    /*
    * [1,2,4,  7,10,11,7,12,6,7,  16,18,19] --> return {3,9}
    * 寻找逆序对：寻找最右逆序对的位置
    * 时间复杂度：O(n) 空间复杂度：O(1)
    * */
    public int[] subSort(int[] array) {
        if (array == null || array.length < 2) return new int[]{ -1, -1 };
        int length = array.length;
        // 从左扫描到右 寻找最右逆序对（正序：逐渐变大）
        int max = array[0];
        int right = -1;
        for (int i = 1; i < length; i++) {
            int value = array[i];
            if (max > value) right = i;
            else max = value;
        }
        // 提前结束
        if (right == -1) return new int[]{ -1, -1 };
        // 从右扫描到左 寻找逆序对（逆序：逐渐变小）
        int min = array[length - 1];
        int left = -1;
        for (int i = length - 2; i >= 0; i--) {
            int value = array[i];
            if (min < value) left = i;
            else min = value;
        }
        return new int[]{ left, right };
    }
}
